Bishkek, Kyrgyzstan - capital of Chuy Province which surrounds the city, though the city itself is not part of the province but rather a province-level unit of Kyrgyzstan
Several other provinces technically have their capitals outside their borders when the cities are classified as highly urbanized (independent); by law these cities are not included in any province, although most of the time these cities are tightly connected and were sometimes once part of the province that surrounds them. See cities of the Philippines for a more extensive explanation and the Virginia entry below for a comparison.
Sindian, China - capital of the province of Fukien, Republic of China from 1956 to 1992, itself located in Taiwan Province. (Before 1956 and after 1992, the capital is Chincheng)